package com.hy.dp.subsequence;

public class MaximumSuborderSum {


    /**
     * 53. 最大子序和
     * 力扣题目链接
     *
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     * 思路
     * 这道题之前我们在讲解贪心专题的时候用贪心算法解决过一次，贪心算法：最大子序和。
     *
     * 这次我们用动态规划的思路再来分析一次。
     *
     * 动规五部曲如下：
     *
     * 确定dp数组（dp table）以及下标的含义
     * dp[i]：包括下标i之前的最大连续子序列和为dp[i]。
     *
     * 确定递推公式
     * dp[i]只有两个方向可以推出来：
     *
     * dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
     * nums[i]，即：从头开始计算当前连续子序列和
     * 一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
     *
     * dp数组如何初始化
     * 从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。
     *
     * dp[0]应该是多少呢?
     *
     * 根据dp[i]的定义，很明显dp[0]应为nums[0]即dp[0] = nums[0]。
     *
     * 确定遍历顺序
     * 递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
     *
     * 举例推导dp数组
     * 以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
     *
     *
     * @param nums
     * @return
     */
    public static int maximumSuborderSum(int [] nums){
        // 1.定义dp数组以及下标
        int [] dp = new int[nums.length + 1];
        //2.推导递推式 递推公式 dp[i] = max (dp[i-1]+nums[i],nums[i]) res = max(res,dp[i])
        //dp[i] = Math.max(do[i-1] + nums[i],nums[i])
        //3.初始化 都为 0
        dp[0] = nums[0];
        int res = nums[0];
        //4.循环遍历
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
            res =  res > dp[i] ? res : dp[i];
        }
        //5.结果推导
        return res;
    }

    public static void main(String[] args) {
        int [] nums = {2,1,-3,4,-1,2,1,-5,4};

        System.out.println("res: "+maximumSuborderSum(nums));
    }
}
